package gold.digger;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC375 {
    public long startExecuteTime = System.currentTimeMillis();


    /*
     * @param 此题目参考了别人代码
     * 这是因为问题情况较为复杂
     * 未来需要再次复习此道题目
     * @return:
     */
//    看到题目的时候，害，二分呗，然后看到竟然有5个提示，发现事情并不这么简单，想了想，和扔鸡蛋一样的题目，因为这种最坏情况，最小，最大，太像扔鸡蛋问题了。
//    动态规划，最大中找最小，好怕这种题。。。头会晕

    class Solution {
        public int getMoneyAmount(int n) {
            return getMoneyAmountRecur(n);
        }

        // 首先不能使用二分思路去做，因为和二分没啥关系，目标数字在任何一个位置都能出现
// 并且每次失败时候的代价也不一样，这题只能用动态规划，类似扔鸡蛋的问题
// 扔鸡蛋是要求F层内确定临界楼层的最坏情况下的最少搜索次数，这题有点类似
// 确定[1:n]内，最坏情况下搜索某个值需要的最少现金值，前者限定了鸡蛋个数，而这一题没有限定搜索次数
// 解法类似，关键是抽象出本题的子问题，考虑第一次搜索选择了[1:n]中的某个数字k，考虑最坏情况下需要的金额
// 如果数字k比目标数字更大，则在左侧搜索，否则应该在右侧搜索，因为是最坏情况，我们选择需要金额更大的一侧
// 取max{左侧，右侧} + k
// 而第一次选择的位置可能是从1到n的任何一个值，因此有
// dp[1][n] = min{max{dp[1][k-1], dp[k+1][n]} + k} 其中k从1枚举到n
// 更一般，我们有 dp[i][j]表示当查找[i:j]范围内的数字需要的至少的现金
// 则dp[i][j] =  min{max{dp[i][k-1], dp[k+1][j]} + k} 其中k从i取到j
// 但是这个dp公式不能从上到下计算，如果从上到下，那么dp[k+1][j]还是未知的
// 考虑从下往上计算，也就是i从n开始，那么dp[k+1][j]肯定已经计算到了
// 还有一点必须注意，i<=j，dp[i][j]中如果i>j，实际上是没有意义的，不用理会，我们也只求了dp中i<=j的哪些情况
        public int getMoneyAmountRecur(int n) {
            int[][] dp = new int[n + 1][n + 1];
            for (int i = n; i >= 1; i--) {
                for (int j = i + 1; j <= n; j++) {
                    int minCost = Integer.MAX_VALUE;
                    for (int k = i + 1; k < j; k++) {
                        minCost = Math.min(minCost, Math.max(dp[i][k - 1], dp[k + 1][j]) + k);
                    }
                    minCost = Math.min(minCost, dp[i + 1][j] + i);
                    minCost = Math.min(minCost, dp[i][j - 1] + j);
                    dp[i][j] = minCost;
                }
            }
            return dp[1][n];
        }
    }


    public void run() {
        Solution solution = new Solution();
        List<Integer> list = new ArrayList<>();
        System.out.println(solution.toString());
    }

    public static void main(String[] args) throws Exception {
        LC375 an = new LC375();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
